Word Break || Word Break II

发表于

Word Break

Question

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

Analysis

  • 数组f[i]表示截止到第i个字符是否满足wordbreak的条件
  • 外层循环从1开始，循环对f[i]进行赋值
  • 内层循环范围为0-i，检查该部分字符串是否存在一个节点j可以使得其满足wordbreak条件
  • 最终返回f[s.length]

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public boolean wordBreak(String s, Set<String> wordDict) {
        boolean[] f=new boolean[s.length()+1];
        Arrays.fill(f,false);
        f[0]=true;
        for(int i=1;i<=s.length();i++){
            for(int j=0;j<i;j++){
                if(f[j]&&wordDict.contains(s.substring(j,i))){
                    f[i]=true;
                    break;
                }
            }
        }
        return f[s.length()];
    }
}

WordBreak II

Question

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

Analysis

My concise JAVA solution based on memorized DFS

11ms C++ solution (concise)

  • 从1开始循环，看[1,length]范围内的子串t是否在字典内，假如在字典内进入递归
  • 对[0,i]范围内的子串进行处理，并返回former
  • 假如former不为空，将former中的串+空格+tmp加入res中，并在最后返回

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
    HashMap<String,List<String>> table=new HashMap<String,List<String>>();
    public List<String> wordBreak(String s, Set<String> wordDict) {
        List<String> res=new ArrayList<String>();
        if(s==null||s.length()==0)
            return res;
        if(table.containsKey(s))
            return table.get(s);
        if(wordDict.contains(s))
            res.add(s);
        for(int i=1;i<s.length();i++){
            String tmp=s.substring(i);
            if(wordDict.contains(tmp)){
                List<String> former=wordBreak(s.substring(0,i),wordDict);
                if(former.size()!=0){
                    for(Iterator<String> ite=former.iterator();ite.hasNext();){
                        res.add(ite.next()+" "+tmp);
                    }  
                }
            }
        }
        table.put(s,res);
        return res;
    }
}